Fitting Voronoi diagrams to planar tesselations

Title: Fitting Voronoi diagrams to planar tesselations
Creator: Aloupis, Greg; Pérez-Rosés, Hebert; Pineda-Villavicencio, Guillermo; Taslakian, Perouz; Trinchet-Almaguer, Dannier
Relation: 24th International Workshop on Combinatorial Algorithms (IWOCA 2013). Combinatorial Algorithms: 24th International Workshop (IWOCA 2013) (Rouen, France 10-12 July, 2013) p. 349-361
Publisher Link: http://dx.doi.org/10.1007/978-3-642-45278-9_30
Publisher: Springer
Resource Type: conference paper
Date: 2013
Description: Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant.
Subject: Voronoi diagram; Dirichlet tesselation; planar tesselation; inverse Voronoi problem
Identifier: http://hdl.handle.net/1959.13/1341045
Identifier: uon:28645
Identifier: ISBN:9783642452772
Language: eng
Reviewed